package EnterpriseAlgorithm.Stack_Queue.Code.NumbersOf_D_Value;

import java.util.LinkedList;

class Solution {
    int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0 || num < 0) {
            return 0;
        }
        LinkedList<Integer> qMin = new LinkedList<>();  //qMin单增，队首存首元素就是同一列的最小
        LinkedList<Integer> qMax = new LinkedList<>(); //qMax单减，队首存首元素就是同一列的最大
        int i = 0;
        int j = 0;
        int res = 0;
        while (i < arr.length) {
            while (j < arr.length) {
                //维持单调递增的对列
                while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[j]) {
                    qMin.pollLast();
                }
                qMin.addLast(j);

                //维持单调递减的对列
                while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[j]) {
                    qMax.pollLast();
                }
                qMax.addLast(j);

                //判断是否有超过num的元素，作为提前结束内层循环条件
                if (arr[qMax.getFirst()] - arr[qMin.getFirst()] > num) {
                    break;
                }
                // 进入下层循环
                j++;
            }

            //i 在移动过程中要去除Min Max为 i 位置上的情况
            if (qMin.getFirst() == i) {
                qMin.pollFirst();
            }
            if (qMax.getFirst() == i) {
                qMax.pollFirst();
            }
            //内层循环结束，计算结果
            res += j - i;
            // 进入外层循环 移动 i
            i++;
        }
        // 外层循环结束，汇总结果
        return res;
    }
}
